We present a protocol that transforms any quantum multi-prover interactiveproof into a nonlocal game in which questions consist of logarithmic number ofbits and answers of constant number of bits. As a corollary, this proves thatthe promise problem corresponding to the approximation of the nonlocal value toinverse polynomial accuracy is complete for QMIP*, and therefore NEXP-hard.This establishes that nonlocal games are provably harder than classical gameswithout any complexity theory assumptions. Our result also indicates that gapamplification for nonlocal games may be impossible in general and provides anegative evidence for the possibility of the gap amplification approach to themulti-prover variant of the quantum PCP conjecture.
展开▼
